package dfs_bfs;
import java.util.*;

import org.junit.Test;
public class Ex647 {
    //错误，根本行不通啊
    class Solutionx {
        public int countSubstrings(String s) {
            int len;
            if (s == null || (len = s.length()) == 0) return 0;
            char[] cs = s.toCharArray();
            return res.size();
        }

        List<String> res = new ArrayList<>();
        public void dfs(String s, int idx, char[] cs) {
            if (idx == cs.length) {
                if (check(s, cs)) res.add(s);
                return;
            }
            String cur;
            res.add(idx + "");
            if (check((cur = s + idx), cs)) res.add(cur);
        }

        public boolean check(String s, char[] cs) {
            int start = s.charAt(0) - '0', end = s.charAt(s.length() - 1);
            if (end - start == 0) return true;
            for (int i = start; i <= ((end - start) >>> 1); i++) {
                if (cs[i] != cs[end - i]) return false;
            }
            return true;
        }
    }

    //动态规划
    /* 
        f[i][j] 表示从i到j中间是否是回文子串

        最终二重循环一次f[i][j]得到为true的数目
    */
    class Solution {
        public int countSubstrings1(String s) {
            int len;
            if (s == null || (len = s.length()) == 0) return 0;
            boolean[][] f = new boolean[len][len];
            int count = 0;
            for (int j = 0; j < len; j++) {
                for (int i = 0; i <= j; i++) {
                    if (i + 1 == j) f[i][j] = s.charAt(i) == s.charAt(j);//相邻字符看是否相等
                    else if (i == j) f[i][j] = true; //单个字符都是
                    else f[i][j] = f[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                    if (f[i][j]) count++;
                }
            }
            return count;
        }

        //空间优化：下一列的更新只与上一列有关，因此可以使用一维向量存储
        public int countSubstrings(String s) {
            int len;
            if (s == null || (len = s.length()) == 0) return 0;
            boolean[] f = new boolean[len];
            int count = 0;
            for (int j = 0; j < len; j++) {
                for (int i = 0; i <= j; i++) {
                    if (i + 1 == j) f[i] = s.charAt(i) == s.charAt(j);//相邻字符看是否相等
                    else if (i == j) f[i] = true; //单个字符都是
                    else f[i] = f[i + 1] && s.charAt(i) == s.charAt(j); //一般位置：当前边缘相同且往中间靠拢一格是回文子串
                    //剩下的情况都默认为false即可

                    if (f[i]) count++;
                }
            }
            return count;
        }
    }

    @Test
    public void test() {
        String s = "abc";
        s = "aaa";
        Solution so = new Solution();
        System.out.println(so.countSubstrings(s));
    }
}
